1537. Полоса

Имеется прямоугольник размера 1×n, квадратики 1×1 которого закрашены белым или черным цветом. По прямоугольнику можно построить "код" - последовательность чисел, равных количеству подряд идущих черных квадратов слева направо.

Например, код этого прямоугольника 2 3 2 8 1. Однако количество белых квадратов нигде не учитывается (группы черных клеток должны разделяться как минимум одной белой клеткой). Поэтому одному и тому же коду может соответствовать несколько прямоугольников. Например, выше приведенному коду также соответствует прямоугольник

Вам необходимо подсчитать количество прямоугольников, удовлетворяющих заданному коду.

Вход. Первая строка содержит количество тестов t (1 < t < 20). Каждая из следующих t строк содержит данные для одного теста. Каждый тест начинается длиной прямоугольника n (1 ≤ n ≤ 200). Затем идет k (0 ≤ k ≤ (n + 1) / 2) – количество чисел в коде. Далее идут k чисел, описывающих непосредственно код.

Выход. Для каждого теста вывести в отдельной строке одно число – количество прямоугольников, удовлетворяющих заданному коду. Ответ всегда помещается в 50 знаковое целое.

Пример входа	Пример выхода
3 4 0 5 2 1 2 4 2 2 2	1 3 0

РЕШЕНИЕ

комбинаторика

Анализ алгоритма

Пусть имеется w белых квадратов и g групп черных квадратов. Поскольку группы черных квадратов не касаются, то должно существовать как минимум g – 1 белых квадратов (если таковых не существует – то ответ 0). При этом w – (g – 1) белых квадратов будут свободными, и их можно расположить в любом месте по отношению к группам черных квадратов. Количество мест, по которым можно расположить свободные белые квадраты, равно (g + 1). Это можно сделать способами. Здесь = – количество способов расположить r одинаковых объектов по n разным местам, где каждое место может содержать произвольное количество объектов (сочетания с повторениями). Таким образом

= =

Пример

Рассмотрим второй тест. Существует три полосы длины 5 с кодом 1 2:

Число свободных белых квадратов равно 1, число групп 2. Следовательно количество мест, куда можно поставить 1 свободный белый квадрат, равно 3. Количество вариантов искомой расстановки равно 3, так как свободный квадрат можно поставить на одно из 3 мест.

Воспользуемся формулой. Число белых квадратов w = 2, число групп g = 2. Количество полос равно = = 3.

Реализация алгоритма

Технически задача сводится к вычислению биномиального коэффициента, значение которого не помещается в 64-битный целый тип. Воспользуемся классом BigInteger.

int n, g, w, group[200];

int i, j, tests;

class BigInteger{ . . .};

BigInteger Cnk(int k, int n)

{

BigInteger res(1);

for(int i = 1; i <= k; i++)

res = res * (n - i + 1) / i;

return res;

}

Читаем количество тестов tests. Для каждого теста считываем код в массив group, параллельно суммируя количество черных квадратов. Вычитаем его из n, получим число белых квадратов w. Если количество белых квадратов w меньше g – 1, то полосы с таким кодом не существует. Иначе вычисляем и выводим результат .

scanf("%d",&tests);

for(i = 0; i < tests; i++)

{

scanf("%d %d",&n,&g);

w = 0;

for(j = 0; j < g; j++)

{

scanf("%d",&group[j]);

w += group[j];

}

w = n - w;

if (w < g - 1) printf("0");

else Cnk(w-g+1,w+1).print();

printf("\n");

}

Java реализация

import java.util.*;

import java.math.*;

public class Main

{

static BigInteger Cnk(BigInteger n, BigInteger k)

{

BigInteger ONE = BigInteger.ONE, CnkRes = ONE;

if (k.compareTo(n.subtract(k)) > 0) k = n.subtract(k);

for(BigInteger i = ONE; i.compareTo(k) <= 0; i = i.add(ONE))

CnkRes = CnkRes.multiply(n.subtract(i).add(ONE)).divide(i);

return CnkRes;

}

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int tests = con.nextInt();

int group[] = new int[200];

while(tests-- > 0)

{

int n = con.nextInt(), g = con.nextInt();

int w = 0;

for(int j = 0; j < g; j++)

{

group[j] = con.nextInt();

w += group[j];

}

w = n - w;

if (w < g - 1) System.out.println("0");

else System.out.println(Cnk(BigInteger.valueOf(w+1),

BigInteger.valueOf(w-g+1)));

}

}

}